//
// Created by Administrator on 2022/2/4.
//

#ifndef CPP_LEARNING_LEETCODE297_H
#define CPP_LEARNING_LEETCODE297_H

#include "treenode.h"
#include <string>
using namespace std;

class Codec297 {
public:
    /**
     *          2
     *      1        3          [[1] 2 [3]]
     *
     *
     *          2
     *      1                      [[1] 2]
     */
     string valToString(int val){
         string s;
         while (val > 0){
             s += '0' + val%10;
             val = val/10;
         }
        return s;
     }
    int stringToVal(string str, int l, int r){
        int val = 0;
        for(int i=l; i<=r; i++){
            val = val * 10 + str[i]-'0';
        }
        return val;
    }


    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root== nullptr) return "";
        string s = "[";
        string leftRe = serialize(root->left);
        string rightRe = serialize(root->right);
        s += leftRe;
        s += valToString(root->val);
        s += rightRe;
        s += "]";
        return s;
    }
    /**
     *      [[1] 2  [3]]
     *      l          r
     */
    void deserializeHelper(string& data, int& index, TreeNode*node) {
        if(index >= data.size()) return ;
        index ++;
        if(data[index] =='['){

            TreeNode* leftNode = new TreeNode;
            node->left = leftNode;
            deserializeHelper(data, index, leftNode);
        }
        int i = 0;
        for( i=index; ; i++){
            if(data[i] ==']' or data[i] =='[') break;
        }

        node->val = stringToVal(data, index, i-1);

        index = i;

        if(data[index] =='['){

            TreeNode* rightNode = new TreeNode;
            node->right = rightNode;
            deserializeHelper(data, index, rightNode);
        }
        //   [[1] 2 [3]]
        //               index 移动到] 后一位
         index ++;

    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()){
            return nullptr;
        }
        int index = 0;
        TreeNode*node = new TreeNode;
        deserializeHelper(data, index,node);
        return  node;
    }
};

void test297(){
    TreeNode * node1 = new TreeNode(1);
    TreeNode * node2 = new TreeNode(2);
    TreeNode * node3 = new TreeNode(3);
    TreeNode * node4 = new TreeNode(4);
    TreeNode * node5 = new TreeNode(5);

    node1->left = node2;
    node1->right = node3;
    node3->left = node4;
    node3->right = node5;

    Codec297 codec297;
    string s = codec297.serialize(node1);

    TreeNode* node = codec297.deserialize(s);

}
#endif //CPP_LEARNING_LEETCODE297_H
